#! /usr/bin/env python
# -*- coding: utf-8 -*-

import heapq

class grafo(object):
    def __init__(self):
        """Grafo implementado como un diccionario de listas"""
        self.cantidad  = 0
        self.aristas   = 0
        self.contenido = {}

    def __str__(self):
        """imprime todo el grafo"""
        """PRE: tanto claves como contenidos tienen el metodo __str__"""
        for nodos in self.contenido:
            print nodos
            for aristas in self.contenido[nodos]:
                print aristas
        return ""

    def cant_nodos(self):
        """retorna la cantidad de nodos en el grafo"""
        return self.cantidad

    def cant_aristas(self):
        """retorna la cantidad de aristas en el grafo"""
        return self.aristas
    
    def agregar_nodo(self,nodo):
        """agrega la clave al grafo sin aristas (salientes)"""
        if (not self.contenido.has_key(nodo)):
            self.contenido[nodo] = []
            self.cantidad+=1
          
    def conectar (self,nodo,destino,peso):
        """conecta 2 elementos"""
        """AVISO: puede existir mas de una arista entre dos nodos"""
        if (self.contenido.has_key(nodo)and self.contenido.has_key(destino)):
            a = arista(destino,peso)
            self.contenido[nodo].append(a)
            self.aristas+=1

    def nodos_inaccesibles(self,nodo):
        """OPCIONAL  1"""
        """devuelve una lista con las claves a las que el nodo no puede acceder en el grafo"""
        def _recorrer_y_marcar (grafo,nodo,dicc):
            """funcion privada de nodos_inaccesibles"""
            """recorre un grafo marcando todos los elementos a los que tiene acceso en un diccionadio"""
            if (not(dicc.has_key(nodo))):
                dicc[nodo] = "marcado"
                for vecinos in grafo.contenido[nodo]:
                    _recorrer_y_marcar(grafo,vecinos.retorna_destino(),dicc)
        l    = []
        dicc = {}
        _recorrer_y_marcar(self,nodo,dicc)
        for claves in self.contenido:
            if (not (dicc.has_key(claves))):
                l.append(claves)
        return l

    def prim (self,nodo,num):
        """retorna un arbol de tendido obtenido a partir del algoritmo de PRIM"""
        """De tratarse de un grafo no dirigido retorna el arbol de tendido minimo"""
        """retornara el arbol en forma de lista de adyacencias, donde se indicara a la raiz como clave=None"""
        def _prim(grafo,nodo,heap,arbol,padre,dicc,num):
            """funcion privada de prim"""
            """utiliza un heap para ir guardando las aristas e ir recorriendo el grafo"""
            """marcando los nodos y agregandolos al "arbol" """
            if (not(dicc.has_key(nodo))):
                dicc[nodo] = "marcado"
                
                if (arbol.has_key(padre)):    #guardamos el nodo en el arbol
                    arbol[padre].append(nodo) 
                else:
                    arbol[padre] = [nodo]
            
                for vecinos in grafo.contenido[nodo]: 
                    heapq.heappush(heap,(vecinos.retorna_peso(num),vecinos.retorna_destino(),nodo)) # lo que agregamos es: (confianza,nodo_destino,padre) 
                while(heap):                                                      # el heap lo ordenara tomando como parametro el 1er elemento (confianza)
                    item = heapq.heappop(heap)  #desencolamos la arista mas chica y repetimos
                    _prim (grafo,item[1],heap,arbol,item[2],dicc,num)   
        arbol = {}
        dicc  = {}
        heap  = []
        _prim(self,nodo,heap,arbol,None,dicc,num)
        return arbol

    def dijstra (self, nodo, num, dicc=None):
        """retorna un diccionario con los caminos minimos respecto al nodo a partir del algoritmo de dijstra """
        """El diccionario que se retorna tendra por clave el nodo destino y como dato el nodo a partir del que se llego"""
        """Para conseguir todo el recorrido, simplemente acceder sucesivamente (usando el dato como clave) """
        """hasta llegar al nodo inicial que tiene como dato None"""
        """PRE: la funcion recibida determina el peso de cada arista"""
        def _dijstra(grafo,nodo,pesos,caminos,dicc):
            """funcion privada de dijstra"""
            if (not(dicc.has_key(nodo))):
                dicc [nodo] = "marcado"
                heap = []
                for arista in grafo.contenido[nodo]:
                    if (pesos[arista.retorna_destino()]>(pesos[nodo]    + arista.retorna_peso(num))): 
                        pesos[arista.retorna_destino()]   = pesos[nodo] + arista.retorna_peso(num) #si el peso del vecino es mayor al del nodo+arista lo cambio por nodo+arista
                        caminos[arista.retorna_destino()] = nodo
                for vecinos in grafo.contenido[nodo]:
                    heapq.heappush(heap,(pesos[vecinos.retorna_destino()],vecinos))
                while(heap):
                    item = heapq.heappop(heap)
                    _dijstra(grafo,item[1].retorna_destino(),pesos,caminos,dicc)#repito hasta que queden todos marcados
            
        pesos   = {}
        caminos = {}
        if not dicc: dicc = {}
        for claves in self.contenido:      #seteo todos los nodos en infinito
            pesos  [claves] = float("inf")
        pesos[nodo] = 0                    #salvo el primero que le pongo 0
        caminos[nodo] = None
        _dijstra(self,nodo,pesos,caminos,dicc)
        return caminos

class arista(object):
	def __init__(self,destino,peso):
	    """clase auxiliar del grafo
            contendra:
                    -espia destino
                    -lista con los pesos de la arista:
                    el caso particular del tp [confianza,tiempo,1]"""
	    """PRE: destino es una clave del grafo,
            confianza y tiempo son enteros positivos"""
	    self.destino     = destino 
            self.peso        = peso
            
	def __str__(self):
            """imprime los datos de la arista"""
	    print "Canal con:",
	    print self.destino
	    print "Nivel de confianza: "+str(self.peso[0])
	    print "Tiempo disponible: "+str(self.peso[1])
	    return ""

	def retorna_destino(self):
            """retorna el parametro destino de la arista"""
            return self.destino

        def retorna_peso(self,num):
            """retorna el peso correspondiente al indice recibido"""
            if (len(self.peso)>num):
                return self.peso[num]
            return 0
